package com.xw.class12;

/**
 * @author XW
 * @data 2023/8/22 15:02
 * @description 判断一棵树是否是平衡二叉树
 *              定义：对于任意一个节点 左子树是平衡二叉树，右子树是平衡二叉树，且左右子树的高度差的绝对值不超过1
 */
public class Code02_IsBalanced {
    class Node{
        public int val;
        public Node left;
        public Node right;

        public Node(int val){
            this.val = val;
        }
    }

    public static boolean isBST(Node head){
        return process(head).balanced;
    }

    private static Info process(Node head) {
        if(null == head){
            return new Info(true,0);
        }
        Info left = process(head.left);
        Info right = process(head.right);
        boolean balanced = true;
        int height = Math.max(left.height, right.height)+1;
        if(!left.balanced){
            balanced = false;
        }
        if(!right.balanced){
            balanced = false;
        }
        if(Math.abs(left.height- right.height) > 1){
            balanced = false;
        }

        return new Info(balanced,height);
    }

    public static class Info{
        boolean balanced;
        int height;

        public Info(boolean balanced,int height){
            this.balanced = balanced;
            this.height = height;
        }
    }
}
